#include <iostream>


using namespace std;

//template<typename Type>
//Type Max(const Type& a, const Type& b)
//{
//	cout << "This is Max<Type>" << endl;
//	return a > b ? a : b;
//}
//
//template<>
//int Max<int>(const int& a, const int& b)
//{
//	cout << "This is Max<int>" << endl;
//	return a > b ? a : b;
//}
//template<>
//char Max<char>(const char& a, const char& b)
//{
//	cout << "This is Max<char>" << endl;
//	return a > b ? a : b;
//}
//
//int Max(const int& a, const int& b)
//{
//	cout << "This is Max" << endl;
//	return a > b ? a : b;
//}
//
////int main()
////{
////	Max(10, 20);
////	Max(12.34, 23.45);
////	Max('A', 'B');
////	Max<int>(20, 30);
////	return 0;
////}
//
//template<class T1, class T2>
//
//class Data
//{
//public:
//	Data() { cout << "Data<T1, T2>" << endl; }
//private:
//	T1 _d1;
//	T2 _d2;
//};
//
//template <class T1>
//class Data<T1, int>
//{
//public:
//	Data() { cout << "Data<T1, int>" << endl; }
//private:
//	T1 _d1;
//	int _d2;
//};
//template <typename T1, typename T2>
//class Data <T1*, T2*>
//{
//public:
//	Data() { cout << "Data<T1*, T2*>" << endl; }
//private:
//	T1 _d1;
//	T2 _d2;
//};
//template <typename T1, typename T2>
//class Data <T1&, T2&>
//{
//public:
//	Data(const T1& d1, const T2& d2)
//		: _d1(d1)
//		, _d2(d2)
//	{
//		cout << "Data<T1&, T2&>" << endl;
//	}
//private:
//	const T1& _d1;
//	const T2& _d2;
//};
//int main()
//{
//	Data<double, int> d1;//T1 int
//	Data<int, double> d2;//T1 T2
//	Data<int*, int*> d3;//
//	Data<int&, int&> d4(1, 2);
//	return 0;
//}
//class A 
//{
//public: void test(float a) 
//{ cout << a; } 
//}; 
//class B :public A 
//{ public: void test(int b) 
//{ cout << b; } 
//}; 
//void main() 
//{ A* a = new A;
//B* b = new B; 
//a = b; 
//a->test(1.1); }
//class A
//
//{
//
//public:
//
//	virtual void f()
//
//	{
//
//		cout << "A::f()" << endl;
//
//	}
//
//};
//
//
//
//class B : public A
//
//{
//
//private:
//
//	virtual void f()
//
//	{
//
//		cout << "B::f()" << endl;
//
//	}
//
//};
//
//int main()
//{
//
//	A* pa = (A*)new B;
//
//	pa->f();
//	return 0;
//}

//class A
//{
//public:
//  A() :m_iVal(0) { test(); }
//  virtual void func() { std::cout << m_iVal <<" "; }
//  void test() { func(); }
//public:
//  int m_iVal;
//};
//class B : public A
//{
//public:
//	B() { test(); }
//	virtual void func()
//	{
//		++m_iVal;
//
//		std::cout << m_iVal << " ";
//
//	}
//
//};




//
//class A 
//{
//public:
//	virtual void func()
//	{
//		cout << "A::void func()" << endl;
//	}
//};
//class B :public A
//{
//public:
//void func()
//{
//	cout << "B::void func()" << endl;
//}
//};
//
//
//
//
//int main()
//
//{
//
//	A* p = new B;
//
//	p->func();
//
//
//	return 0;
//
//}

vector<vector<int>> levelOrder(TreeNode* root)
{
    vector<vector<int>> vv;
    if (root)
        return vv;
    vector<int> v;
    queue<TreeNode*> q1;
    queue<TreeNode*> q2;

    q1.push(root);

    while (!q1.empty() || !q2.empty())
    {
        while (!q1.empty())
        {
            TreeNode* front = q1.front();
            v.push_back(front->val);
            q1.pop();

            if (front->left)
                q2.push(front->left);
            if (front->right)
                q2.push(front->right);

        }

        while (!q2.empty())
        {
            TreeNode* front = q2.front();
            v.push_back(front->val);
            q2.pop();

            if (front->left)
                q1.push(front->left);
            if (front->right)
                q1.push(front->right);

        }
        vv.push_back(v);
        v.clear();
    }

    return vv;
}

int main()
{

    return 0;
}